Beyond Descriptive Modelling of Network Degrees: Tail-Realistic Preferential Attachment

Thomas Boughen

October 31, 2025

The scale-free debate

A network is scale-free if the tail of the degree distribution follows a power-law.

\[ \Pr(K>k) = \bar F(k) \sim k^{-\gamma} \]

Scale-free Degree Distribution — Orginal scale

Scale-free Degree Distribution — Log scale

There has been a heated debate over the presence of scale-free networks in reality.

Modelling the degrees

Power Law

Tail Estimation

Mixture Model

Mixture Model

Zipf-Polylog

\[ f(k) \propto x^{-\alpha} \theta^x, \qquad x=1, 2, \ldots, u \]

Integer Generalised Pareto

\[ F(k)= 1-\left(1+\frac{\xi(k-u)}{\sigma +\xi u}\right)_+^{-1/\xi}, \qquad x=u+1,\ldots \]

Using this model @Lee24 found that networks often have a heavy tail but not quite as heavy as implied by the body.

Why care about scale-freeness?

Many use scale-freeness of a network to justify the mechanics behind the network’s growth.

Preferential Attachment (rich-get-richer) \(\Rightarrow\) Power-law degree distribution

but

Power-law degree distribution \(\nRightarrow\) Preferential Attachment (rich-get-richer)

This is fairly common as modelling the degrees does not generally inform the network growth.

Aims

  • Propose a flexible tail-realisitic model for network degrees
  • Obtain information about network growth from degrees alone

Preferential Attachment

Example

Steps

  1. Node added to network
  2. Connects to \(m\) existing nodes with weights \(\pi_i\):

\[ \pi_i = \left. k_i \middle/ \sum k_j \right. \] where \(k_i\) is degree of node \(i\).

Results in a power-law degree distribution

\[ \bar F(k)\sim k^{-2} \]

General Preferential Attachment

Example

Steps

  1. Node added to network
  2. Connects to \(m\) existing nodes with weights \(\pi_i\):

\[ \pi_i = \left. b(k_i) \middle/ \sum b(k_j) \right. \] where \(k_i\) is degree of node \(i\).

How do we study the degree distribution of this?

Branching Process

Consider a CTBP \(\zeta(t)\) driven by Markovian pure birth process

\[ \Pr(\zeta(t+\text{d}t) = k+1 | \zeta(t) =k) = b(k) \text{d}t + o(\text{d}t) \]

Construct tree \(\Upsilon(t)\) determined by \(\zeta(t)\), where each node in the tree has birth rate \(b(\text{deg}(x,\Upsilon(t)))\).

Then the tail of the limiting degree distribution is:

\[ \bar F(k) = \lim_{t\rightarrow \infty} \frac{\sum_{x\in\Upsilon(t)}\mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}>k\right\}}{ \sum_{x\in\Upsilon(t)} \mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}\ge 0\right\}\right\}} \]

Now applying a result from [Rudas et al.]

Rudas result

For a characteristic \(\phi\) of the tree \(\Upsilon(t)\):

\[ \lim_{t\rightarrow\infty} \frac{1}{\left|\Upsilon(r)\right|}\sum_{x\in\Upsilon(t)}\phi(\Upsilon(t)_{\downarrow x}) = \lambda^* \int_0^\infty e^{-\lambda^*}\mathbb E \left[\phi(\Upsilon(t))\right]\text{d}t \]

\[ \bar F(k) = \frac{\int_0^\infty e^{-\lambda^*t}\mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}>k\right\}\text{d}t }{\int_0^\infty e^{-\lambda^* t} \text{d}t} = \prod_{i=0}^k \frac{b(i)}{\lambda^* + b(i)},\quad k=0,1,2, \ldots \]

Studying the tail

We want to pay careful attention to the extreme values

Studies of empirical degrees often use methods from continuous extremes

As this is a discrete distribution we need some new machinery.

Continuous Extremes Recap

Maximum Domains of Attraction

Frechet (heavy tailed)

\[ \bar F(x) = x^{-\gamma} L(x) \] e.g. Pareto, Cauchy, Lévy

Gumbel (light-tailed)

\[ \lim_{x\rightarrow\infty}\frac{\bar F (x + t a(x))}{\bar F(x)}= e^{-t} \] e.g. Exponential, Normal, Gamma

  • The Frechet is equivalent to regular variation with tail-index \(\gamma\)
  • Also equivalent to scale-free or power-law

All continuous distributions with infinite right endpoint fall into one of these.

Many discrete distributions don’t satisfy the conditions to belong to an MDA

Discrete Extremes

[Shimura] uses the following quantity to categorise discrete distributions \[ \Omega(F, k) = \left(\log \frac{\bar F(k+1)}{ \bar F(k+2)}\right)^{-1} - \left(\log \frac{\bar F(k)}{ \bar F(k+1)}\right)^{-1} \]

Frechet

\[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\alpha \] and \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \]

Recoverable to Gumbel

\[ \lim_{k\rightarrow\infty} \Omega(F,k) = 0 \] and \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} \neq 1 \]

Gumbel

\[ \lim_{k\rightarrow\infty} \Omega(F,k) = 0 \] and \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \]

Analysing GPA degrees

Now we can use the limiting survival function of a GPA model to show that:

\[ \lim_{k\rightarrow\infty} \Omega(F,k)= \begin{cases} \lim_{k\rightarrow \infty}\frac{b(k+1)-b(k)}{\lambda^*}, &\text{when } b(k) \rightarrow \infty\\ 0, &\text{otherwise} \end{cases} \]

Examples

Barabasi-Albert (BA) \[ b(k) = k+1 \] \[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\lambda^* = 1/2 \] \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \] Frechet, with index 2

Uniform \[ b(k) = c \] \[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\lambda^* = 0 \] \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 0 \] Recoverable to Gumbel

Polynomial \[ b(k) = (k+1)^\alpha \] \[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\lambda^* = 0 \] \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \] Gumbel

What we have learned so far.

\[ \lim_{k\rightarrow\infty} \Omega(F,k)= \begin{cases} \lim_{k\rightarrow \infty}\frac{b(k+1)-b(k)}{\lambda^*}, &\text{when } b(k) \rightarrow \infty\\ 0, &\text{otherwise} \end{cases} \]

  • Empirical degree distributions are heavy-tailed but exhibit more nuanced behaviour than obtained by BA model
  • For degree distribution to be heavy tailed and be the result of a GPA model, preference must be eventually “linear” like in the BA model

Constructing a new preference function

We require something that is eventually linear but is flexible enough for real networks

Barabasi-Albert \[ b(k) = k+1 \]

Proposed Model \[ b(k) = \begin{cases} k^\alpha + \varepsilon, &k\le k_0\\ k_0^\alpha + \varepsilon + \beta(k-k_0), &k>k_0 \end{cases} \]

\[ \bar F(k) = \frac{2}{(k+2)(k+3)} \]

\[ \bar F(k) = \begin{cases} \prod_{i=0}^{k}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon},&k\le k_0,\\ \left(\prod_{i=0}^{k_0-1}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon}\right)\frac{\Gamma(\lambda^*+k_0^\alpha + \varepsilon)/\beta)}{\Gamma\left((k_0^\alpha + \varepsilon)/\beta\right)} \frac{\Gamma\left(k-k_0 + 1 +\frac{k_0^\alpha + \varepsilon}{\beta}\right)}{\Gamma\left(k-k_0 + 1 +\frac{\lambda^* +k_0^\alpha + \varepsilon}{\beta}\right)},&k > k_0, \end{cases} \]

Shape of degree distribution

Tail behaviour

% heat map plot

\[ \lim_{k\rightarrow\infty} \Omega(F, k) = \beta / \lambda^*, \qquad \lim_{k\rightarrow\infty} \bar F(k+1)/ \bar F(k) = 1 \]

All limiting degree distributions produces by this model are Frechet with tail-index \(\lambda^*/\beta\).

Connection to Existing Method

We can find that: \[ \bar F(k) \begin{cases} =\prod_{i=0}^{k}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon},&k\le k_0,\\ \approx \left(\prod_{i=0}^{k_0}\frac{i^\alpha + \varepsilon}{\lambda^* + i^\alpha + \varepsilon}\right)\left(\frac{\beta(k-k_0)}{k_0^{\alpha}+\varepsilon+\beta} + 1\right)^{-\lambda^{*}/\beta},&k > k_0, \end{cases} \]

that is, conditional degree distribution is approximated by:

\[ \text{IGP}\left(\frac{\beta}{\lambda^*}, \frac{k_0^\alpha + \varepsilon+\beta}{\lambda^*},k_0\right) \]

a distribution used by [Lee] for modelling network degrees.

Unfortunately we can’t go from the IGP fit to the model parameters.

Simulation Study - set up

  1. Simulate networks
  2. Use likelihood to fit model
  3. Recover parameters

The simulated data

  • 100,000 nodes
  • 36 parameter combinations
  • \(k_0\) fixed at \(20\)
  • Only using final degrees

The likelihood

\[ \begin{aligned} L(\pmb n | \pmb \theta,l) = &\left(\frac{\lambda^*}{\lambda^*+\varepsilon}\right)^{n_0}\left(\prod_{j=l}^{k_0-1}\frac{j^\alpha +\varepsilon}{\lambda^* + j^\alpha +\varepsilon}\right)^{\left(\sum_{i\ge k_0}n_{i}\right)} \\ &\times \prod_{l \le i<k_0}\left(\frac{\lambda^*}{\lambda^* +i^\alpha + \varepsilon } \prod_{j=l}^{k_0-1}\frac{j^\alpha + \varepsilon}{\lambda^* + j^\alpha + \varepsilon}\right)^{n_i}\\ &\times \prod_{i\ge k_0}\left(\frac{\text{B}(i-k_0 + (k_0^\alpha + \varepsilon)/\beta,1+\lambda^*/\beta)}{\text{B}((k_0^\alpha + \varepsilon)/\beta,\lambda^*/\beta)}\right)^{n_i}, \end{aligned} \]

Priors

\[\begin{align*} \alpha&\sim \text{Gamma}(1,0.01),\\ \beta &\sim \text{Gamma}(1,0.01),\\ k_0 &\sim \text{U}(1,10,000),\\ \varepsilon &\sim \text{Gamma(1,0.01)}, \end{align*}\]

Now we use an adaptive Metroplis-Hastings to obtain posterior samples

Model fits

%show model fitting the degree distribution well

The results

\(\alpha\) posterior

The results

\(\varepsilon\) posterior

The results

\(k_0\) posterior

The results

\(\beta\) posterior

Real Data

Internet

Flights

Proteins

Data sourced from Network Data Repository[@nr]

We will fit the model and compare it to the mixture model.

Fitting to Real Data

Bonus Information

Key Results

  • Characterisation of degree distribution from preference function
    • Eventually linear \(\rightarrow\) Frechet (heavy tail)
    • Sublinear and unbounded \(\rightarrow\) Gumbel (light tail)
    • Bounded \(\rightarrow\) recoverable to Gumbel (light tail)
  • Proposed preference function gives tail-realistic degree distributions
  • Parameters recovered from degrees alone in simulated networks
  • Can learn about real networks growth from snapshot of degrees

Limitations and Future work

  • Theory based on trees, which real networks rarely are

  • Only consider degrees in the snapshot

  • Assume a fairly restrictive model (pure birth)

  • Look beyond just the degrees

  • Incorporate more complex behaviour into the growth model

  • Extend theory beyond that of trees

Thank you